#
# @lc app=leetcode.cn id=69 lang=python3
#
# [69] x 的平方根
#

# @lc code=start
class Solution:
    def mySqrt(self, x: int) -> int:
        left = 0
        right = x
        mid = -1

        while left <= right:
            mid = int((right - left)/2)

            if (left + mid)**2  <= x and (left + mid + 1)**2 > x:
                return left + mid
            elif x > (left + mid)**2:
                left = left + mid + 1
            else:
                right = left + mid - 1
# @lc code=end
